package practise.alogrithm.hundredInterviewQuestions.secondTime;

/**
 * Created by Richard on 7/25/2014.
 */
public class MaxSumOfAArray {
    public Integer maxSum(Integer[] array){
        Integer maxSum = Integer.MIN_VALUE;
        Integer sum = Integer.MIN_VALUE;
        Integer startIndex=0;
        Integer endIndex=0;
        Integer index =0;
        int tempStart = 0;
        for(Integer value : array){

            if((sum+value)<value){
                sum=value;
                tempStart=index;
            }
            else{
                sum+=value;
            }
            if(maxSum<sum){
                startIndex = tempStart;
                maxSum =sum;
                endIndex=index;
            }
            index++;
        }
        System.out.println("Start:" + startIndex + ":end:" + endIndex);
        return maxSum;
    }

    public static void main(String[] args){
        MaxSumOfAArray maxSumOfAArray = new MaxSumOfAArray();
        System.out.println(maxSumOfAArray.maxSum(new Integer[]{1,-2,3,10,-4,7,2,-5}));
    }
}
